package com.algorithms.techniques.graph;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import org.apache.commons.collections15.Transformer;

import com.algorithms.absdatatypes.IDisjointSet;

import edu.uci.ics.jung.graph.DirectedSparseMultigraph;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.util.Pair;

public class KruskalSpanningTree<V,E extends Comparable> implements SpanningTree<V,E> {

	
	public Graph<V,E>  createSpanningTree(Graph<V,E> graph) {
		
		
		Graph<V,E> spanningTree = new DirectedSparseMultigraph<V, E>();
		List<E> kruskalEdges = new ArrayList<E>();
		kruskalEdges.addAll(graph.getEdges());
		// Sort the edges in ascending order
		
		Collections.reverse(kruskalEdges);
		// Prepare the disjoint set
		IDisjointSet<V> disjointSet = new DisjointSet<V>();
		for (V vertex : graph.getVertices()) 
		{
			disjointSet.makeSet(vertex);
		}
		// Iterate through the edges 
		for (E edge : kruskalEdges) 
		{
			Pair<V> pair=graph.getEndpoints(edge);
			if (disjointSet.findSet(pair.getFirst()) != disjointSet
					.findSet(pair.getSecond())) 
			{
				disjointSet.union(pair.getFirst(), pair.getSecond());
				spanningTree.addVertex(pair.getFirst());
				spanningTree.addVertex(pair.getSecond());
				spanningTree.addEdge(edge, pair.getFirst(), pair.getSecond());
			}
		}
		return spanningTree;
	}

}
